ABC038 D - プレゼント

https://atcoder.jp/contests/abc038/tasks/abc038_d

提出

code: python

n = int(input())

wh = sorted(list(map(int, input().split())) for _ in range(n))

# これが最適とは限らない

# 制約 10^5

# 単調に上がっていく最大値

tmp_h = wh01

tmp_w = wh00

ans = 1

res = 1

for i in wh:

if (i1 > tmp_h and i0 > tmp_w):

res += 1

if (res > ans):

ans = res

else:

res = 1

tmp_w = i0

tmp_h = i1

print(ans)

解答

code: python

import bisect

n = int(input())

wh = list(map(int, input().split())) for _ in range(n)

# w でソートすれば w に関しては単調増加になるので、 h を適切に選んで最大の単調増加列を作る

# w が等しいものを単調増加列に含めないようにする必要がある。これは w が等しい部分を降順ソートしておくことで回避できる。

# lis = 1, 2, INF が、 w = 2 の h である場合を打ち消すために、 w = 2 の h は lis = 1, INF となるようにする。

wh.sort(key=lambda x: (x0, -x1))

# print(wh)

# 2, 2], 2, 1, 4, 2, 5, 3, [8, 8

INF = 10000000

lis = INF for _ in range(n+1)

for i in range(n):

lis[bisect.bisect_left(lis, whi1)] = whi1

# print(lis)

# 1, 2, 3, 8, 10000000, 10000000

print(bisect.bisect_left(lis, INF)) # 4

テーマ

メモ

提出

AC/WA

code: python

n = int(input())

wh = list(map(int, input().split())) for _ in range(n)

wh.sort(reverse=True)

ans = 1

tmpw = wh00

tmph = wh01

for i in range(1, n):

w, h = whi

if w < tmpw and h < tmph:

ans += 1

tmpw = w

tmph = h

print(ans)